package dp;

import java.util.Arrays;

public class D230825 {
    // 买卖股票的最好时机(一)

    // 总共只能买入和卖出一次

    // 动态规划
    // 时间: O(N)
    // 空间: O(N)
    public int maxProfit (int[] prices) {
        int n = prices.length;
        // dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2];
        // 第一天不持股，总收益为0
        dp[0][0] = 0;
        // 第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0];

        // 遍历后续每天，状态转移
        for(int i = 1; i < n; i++){

            // 不持股，可能是前一天就不持股，也可能是今天卖了
            // max(前一天不持股的收益，前一天持股的收益 + 今天卖了的收益)
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

            // 持股，可能是前一天就已经持股了，今天第一次买入
            // max(前一天持股收益，今天买入的收益)
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0];
    }

    // 贪心算法
    // 时间: O(N)
    // 空间: O(1)
    public int maxProfit2 (int[] prices) {
        // 维护最大收益
        int res = 0;
        // 排除特殊情况
        if(prices.length == 0)
            return res;
        // 维护最低股票价格
        int Min = prices[0];
        // 遍历后续股票价格
        for(int i = 1; i < prices.length; i++){
            // 如果当日价格更低则更新最低价格
            Min = Math.min(Min, prices[i]);
            // 维护最大值
            res = Math.max(res, prices[i] - Min);
        }
        return res;
    }




    // 买卖股票的最好时机(二)

    // 可以多次买卖该只股票，但是再次购买前必须卖出之前的股票

    // 动态规划
    // 时间: O(N)
    // 空间: O(N)
    public int maxProfit3 (int[] prices) {
        int n = prices.length;
        // dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2];
        // 第一天不持股，总收益为0
        dp[0][0] = 0;
        // 第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0];

        // 遍历后续每天，状态转移
        for(int i = 1; i < n; i++){
            // 不持股，可能是前一天就不持股了，也可能是今天卖掉了
            // max(前一天不持股的收益，前一天持股的收益 + 今天卖了的收益)
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

            // 持股，前一天就已经持股了，或前一天不持股，今天买入的（可以多次买卖，但是买入之前要先卖出之前的）
            // max(前一天持股的收益，前一天没持股的收益 + 今天买入的收益)
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0];
    }

    // 贪心算法
    // 时间: O(N)
    // 空间: O(1)
    public int maxProfit4 (int[] prices) {
        int res = 0;
        for(int i = 1; i < prices.length; i++){
            // 只要某段在递增就有收益
            if(prices[i - 1] < prices[i])
                // 收益累加
                res += prices[i] - prices[i - 1];
        }
        return res;
    }


    // 买卖股票的最好时机(三)

    // 最多可以对该股票有两笔交易操作
    // 一笔交易代表着一次买入与一次卖出
    // 进行第二笔交易之前，需要先结束第一笔交易

    // 动态规划
    // 时间: O(N)
    // 空间: O(N)
    public int maxProfit5 (int[] prices) {
        int n = prices.length;
        // dp[i][0] 表示到第 i 天为止，没有买过股票的最大收益
        // dp[i][1] 表示到第 i 天为止，买过一次股票还没有卖出的最大收益
        // dp[i][2] 表示到第 i 天为止，买过一次也卖出过一次股票的最大收益
        // dp[i][3] 表示到第 i 天为止，买过两次只卖出过一次股票的最大收益
        // dp[i][4] 表示到第 i 天为止，买过两次同时也买出过两次股票的最大收益
        int[][] dp = new int[n][5];
        // 初始化dp为最小
        Arrays.fill(dp[0], -10000);
        // 第 0 天不持有状态
        dp[0][0] = 0;
        // 第 0 天持有股票
        dp[0][1] = -prices[0];

        // 状态转移
        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i - 1][0];

            // 买过一次股票的收益 = max(昨天就是已经买过一次了，今天才买的)
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            // 完成一笔交易的收益 = max(昨天就已经完成了，今天才卖出的)
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            // 第两笔交易买入的收益 = max(昨天的，今天才进行第二笔交易的买入)
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            // 完成两笔交易的收益 = max(昨天就完成了，今天才进行第二笔交易的卖出)
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }

        // 选取最大值，可以只进行一笔交易
        return Math.max(dp[n - 1][2],Math.max(0, dp[n - 1][4]));
    }
}
